import java.util.*;

class Node<E> {

   E		data;
   Node<E>		previous, next;
 
   public Node( E obj ) { data =  obj; previous = next = null; }
}

public class MyList <E> {
 
    class MyListIterator implements Iterator<E> {
	Node<E> cur = head;
	boolean	dir ;
	public MyListIterator ( ) { };
	public MyListIterator ( boolean dir ) { 
	    this.dir = dir;
	    cur = dir? head : tail;
	};
	public boolean hasNext() { return cur != null; }
	public E    next () { 
	    E obj = cur.data;
	    cur   = dir ? cur.next : cur.previous;
	    return obj;
	}
	public void remove( ) { }

    }

    public Iterator<E> iterator( ) { return iterator(true); }
    public Iterator<E> iterator( boolean direction ) { return new MyListIterator( direction ) ; }

    protected  int		count;
    protected	Node<E>		head, tail;

    public MyList ( ) {
	count = 0; head = tail = null;
    }

    public boolean empty ( ) {  return count == 0 ; }
    public int	   size( )   { return count ; } 

    MyList<E> insert ( E obj, int pos ) {
	Node<E> nn = new Node<E>( obj );
	if ( count == 0 ) {
		head = tail = nn;
	} else if ( pos < 1 ) {   // insert in the front
		  nn.next = head; head.previous = nn; head = nn;
	} else if ( pos >= count ) {  // add the new node to the end.
		  tail.next = nn; nn.previous = tail; tail = nn;
	} else {   // add new node in the middle.
	     Node<E> cur = head;
	     for ( int i = 1; i < pos; i++ ) cur = cur.next;
	     nn.previous = cur; nn.next = cur.next;
	     cur.next = nn; nn.next.previous = nn;
	}
	count ++;
	return this;
    }

    E 		remove ( int pos ) {
	E obj = null;
	if ( count < 1 || pos < 0 || pos >= count ) return null;    // no object in the list
        else if ( count == 1) {		// There is only one item in the list
		obj = head.data;
		head = tail = null;
	} if ( pos == 1 ) { 		// remove the first item, and the list must have at least 2 items.
		obj = head.data;
		head = head.next;
		head.previous.next = null;
		head.previous      = null;
	} if  ( pos == count - 1 ) {   // remove the last node and list has at least 2 items
		obj = tail.data;
		tail = tail.previous;
		tail.next.previous = null;
		tail.next = null;
	} else { 
		Node<E> cur = head.next; // cur reference to second node whose position is 1.
		for ( int i = 1; i < pos ; i ++ ) cur = cur.next;
		cur.previous.next = cur.next;
		cur.next.previous = cur.previous;
		cur.next = cur.previous = null;
	}
	count --;
	return obj;

    }
}